package com.test.daily.leetcode.y2022.m07.day0714.v03;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;

/**
 * @descriptions:
 * @author: Tom
 * @date: 2022/7/14 下午 01:22
 * @version: 1.0
 */
public class Solution {
    public static class HeapGreater<T> {
        public ArrayList<T> heap;
        public HashMap<T, Integer> map;
        public int heapSize;
        public Comparator<? super T> comparator;

        public HeapGreater(Comparator c) {
            this.comparator = c;
            heap = new ArrayList<>();
            heapSize = 0;
            map = new HashMap<>();
        }

        public boolean isEmpty(){
            return heap.size() == 0;
        }

        public void push(T value){
            this.heap.set(heapSize, value);
            this.map.put(value, heapSize);
            heapInsert(heapSize--);
        }
        public T pop(){
            T ans = heap.get(0);
            map.remove(0);
            swap(0, heapSize - 1);
            heapify(heapSize--);
            return ans;
        }

        public void remove(T target){
            T replace = heap.get(heapSize-1);
            int index = map.get(target);
            heap.remove(replace);
            map.remove(--heapSize);
            if(target != replace){
                heap.set(index, replace);
                map.put(replace, index);
                resign(index);
            }
        }

        public void resign(int index){
            heapify(index);
            heapInsert(index);
        }

        public void swap(int i, int j) {
            T o1 = heap.get(i);
            T o2 = heap.get(j);
            map.put(o1, j);
            map.put(o2, i);
            heap.set(i, o2);
            heap.set(j, o1);
        }

        public void heapInsert(int index) {
            while (comparator.compare(heap.get(index), heap.get((index - 1) / 2)) < 0) {
                swap(index, (index - 1) / 2);
                index = (index - 1) / 2;
            }
        }

        public void heapify(int index){
            int left = index * 2 + 1;
            while(left < heapSize){
                int largest = left + 1 < heapSize && comparator.compare(heap.get(left), heap.get(left+1)) < 0?
                        left +1: left;
                largest = comparator.compare(heap.get(largest), heap.get(index)) < 0 ? index: largest;
                if(largest == index){
                    break;
                }
                swap(largest, index);
                index = largest;
                left = index * 2 + 1;
            }
        }

    }
}
